package 分类.二维动归;

public class 背包问题 {



    //01背包
    //二维dp
    public static int testweightbagproblem(int[] weight, int[] value, int bagsize){
        int len=weight.length;
        int res=0;
        int [][] dp=new int[len+1][bagsize+1];
        for (int i=0;i<=len;i++){
            for (int j=0;j<=bagsize;j++){
                if(bagsize<weight[i]){
                    dp[i][j]=dp[i-1][j];
                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]+value[i]]);
                }
                res=Math.max(res,dp[i][j]);
            }
        }
        return res;
    }


    //一维dp
    public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
        int len=weight.length;
        int[] dp=new int[bagWeight+1];
        for (int i=0;i<len;i++){
            for (int j=bagWeight;j>=weight[i];j--){
                dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[j]);
            }
        }
    }
}
